package _0787_Cheapest_Flights_Within_K_Stops;

import java.util.Arrays;

/**
 * Date: 2021/8/24 9:58
 * 执行用时：7 ms, 在所有 Java 提交中击败了56.48%的用户
 * 内存消耗：39.5 MB, 在所有 Java 提交中击败了66.18%的用户
 */
public class Solution {

    static final int N = 110, INF = 0x3f3f3f3f;
    int[] dist = new int[N], backup = new int[N];

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int i = 0; i <= k; i++) {
            System.arraycopy(dist, 0, backup, 0, dist.length);
            for (int[] edge : flights) {
                int a = edge[0], b = edge[1], w = edge[2];
                dist[b] = Math.min(dist[b], backup[a] + w);
            }
        }
        if (dist[dst] > INF / 2) return -1;
        return dist[dst];
    }

    public static void main(String[] args) {

        int[][] flights = {
                {0, 1, 100},
                {1, 2, 100},
                {0, 2, 500}
        };
        System.out.println((new Solution()).findCheapestPrice(3, flights, 0, 2, 1));  // 200
    }
}
